#include "evaluate.h"

extern int gridUnit;
extern int x_gridNum;
extern int y_gridNum;
extern int numBins;
extern ckt this_ckt;
extern double HPWL, penalty, displacement, max_displacement, targUt;
extern string directory;
extern vector<double> util_array;

void reduce_density_check(ckt & ptrckt, double T1, double T2, int T3)
{

	tinyRow_setup(ptrckt);

	int binArea = gridUnit * gridUnit;
	int extra_area;
	Candidate temp;
	// Need to clean up?
	
	for(int i = 0; i < numBins; i++)
	{
		if(util_array[i] > T1 * targUt)
		{
			extra_area = binArea * (util_array[i] - targUt);
			queue<Candidate> qu;
			// Preparation
			for(int row = 0; row < 9; row++)
			{
				int tinyRow_ID = index_translate(i, row);
				tinyRow & this_row = ptrckt.tinyRows[tinyRow_ID];
				if(this_row.isValid == false || this_row.NodeID.size() == 0)
				{
					continue; 
				}
				else
				{
					vector<int>::iterator it;
					for(it = this_row.NodeID.begin(); it != this_row.NodeID.end(); ++it)
					{
						if(ptrckt.nodes[*it].isFixed)
							continue;
						else // Calculate the optimal region for this node
						{
							temp.cur_node = & ptrckt.nodes[*it];
							temp.src_row = & this_row;
							while(!temp.dest_row.empty())
								temp.dest_row.pop();
							if(calculate_candidate_check(ptrckt, temp, T2))
								qu.push(temp);
						}
					}
				}
			}
			// Move cells out of congested region
			while(!qu.empty() && extra_area > 0)
			{
				temp = qu.front();
				qu.pop();
				while(temp.dest_row.empty() == false)
				{
					tinyRow * dest = temp.dest_row.front();
					temp.dest_row.pop();

					int best_x = -1;
					int target_HPWL_reduction = T3;
					bool flag = false;
					while(best_x == -1 && target_HPWL_reduction < 0)
					{
						best_x = insert2tinyRow_check(ptrckt, *(temp.cur_node), *dest, target_HPWL_reduction);
						if(best_x != -1)
						{
							if(insert2site_check(ptrckt, *(temp.cur_node), *dest, best_x)) // Need check
							{
								int cur_area = (temp.cur_node)->width * (temp.cur_node)->height;
								extra_area -= cur_area;
								util_array[i] -= (double)cur_area / (gridUnit * gridUnit);
								util_array[rowid2binID(dest->ID)] += (double)cur_area / (gridUnit * gridUnit);
								assert(util_array[i] >= -0.05);
								assert(util_array[rowid2binID(dest->ID)] <= 1.05);
								erase_src_node(ptrckt, *(temp.src_row), (temp.cur_node)->ID);
								flag = true;
								break;
							}
						}
						target_HPWL_reduction += 10;
					}
					if(flag)
						break;
				}
			}
		}
	}
}

bool calculate_candidate_check(ckt & ptrckt, Candidate & temp, double T2)
{
	// Calculate the optimal region, using median method
	node & this_node = *(temp.cur_node);
	tinyRow & this_row = *(temp.src_row);
	if(this_node.isFixed)
		return false;

	int srcBinID = rowid2binID(temp.src_row->ID);
	assert(srcBinID >= 0 && srcBinID <= numBins);

	// Consider the three bins on its left side
	if(srcBinID % x_gridNum != 0)
	{
		int curBinID = srcBinID - 1;
		if(util_array[curBinID] < T2 * targUt)
		{
			addBin2Queue(ptrckt, curBinID, temp, this_row);
		}
		if(srcBinID >= x_gridNum) // Has a row of bins beneath it
		{
			int curBinID = srcBinID - 1 - x_gridNum;
			assert(curBinID >= 0);
			if(util_array[curBinID] < T2 * targUt)
			{
				addBin2Queue(ptrckt, curBinID, temp, this_row);
			}
		}
		if(srcBinID < numBins - x_gridNum) // Has a row of bins above it
		{
			int curBinID = srcBinID - 1 + x_gridNum;
			assert(curBinID <= numBins - 1);
			if(util_array[curBinID] < T2 * targUt)
			{
				addBin2Queue(ptrckt, curBinID, temp, this_row);
			}
		}
	}
	// Consider the three bins on its right side
	if(srcBinID % x_gridNum != x_gridNum - 1)
	{
		int curBinID = srcBinID + 1;
		if(util_array[curBinID] < T2 * targUt)
		{
			addBin2Queue(ptrckt, curBinID, temp, this_row);
		}
		if(srcBinID >= x_gridNum) // Has a row of bins beneath it
		{
			int curBinID = srcBinID + 1 - x_gridNum;
			assert(curBinID >= 0);
			if(util_array[curBinID] < T2 * targUt)
			{
				addBin2Queue(ptrckt, curBinID, temp, this_row);
			}
		}
		if(srcBinID < numBins - x_gridNum) // Has a row of bins above it
		{
			int curBinID = srcBinID + 1 + x_gridNum;
			assert(curBinID <= numBins - 1);
			if(util_array[curBinID] < T2 * targUt)
			{
				addBin2Queue(ptrckt, curBinID, temp, this_row);
			}
		}
	}
	// Consider the bin beneath it
	if(srcBinID >= x_gridNum)
	{
		int curBinID = srcBinID - x_gridNum;
		if(util_array[curBinID] < T2 * targUt)
		{
			addBin2Queue(ptrckt, curBinID, temp, this_row);
		}
	}
	// Consider the bin above it
	if(srcBinID < numBins - x_gridNum)
	{
		int curBinID = srcBinID + x_gridNum;
		if(util_array[curBinID] < T2 * targUt)
		{
			addBin2Queue(ptrckt, curBinID, temp, this_row);
		}	
	}

	if(temp.dest_row.size() != 0)
		return true;
	else
		return false;
}

int insert2tinyRow_check(ckt & ptrckt, node & this_node, tinyRow & dest_row, int threshold)
{
	if(this_node.isFixed)
		return -1;

	int best_x = -1;
	int best_reduction = threshold;
	int x = this_node.x_coord; // Original x
	int y = this_node.y_coord; // Original y
	int i;
	query answer;

	int min_distance;
	if(this_node.initial_x >= dest_row.lx && this_node.initial_x <= dest_row.rx)
		min_distance = abs(dest_row.y - this_node.initial_y);
	else
	{
		min_distance = min(cell_displacement(dest_row.lx, dest_row.y, this_node),
								cell_displacement(dest_row.rx - this_node.width, dest_row.y, this_node));
	}

	if(min_distance > max_displacement * 0.9)
	{
		return -1;
	}

	// Strategy: Only examine the left end of each blank space
	if(space_query(ptrckt, this_node, dest_row, 0, answer) && answer.space >= this_node.width)
	{	
		if(cell_displacement(dest_row.lx, dest_row.y, this_node) <= max_displacement * 0.9)
		{
			int reduction = delta_HPWL(ptrckt, this_node.ID, dest_row.lx - x, dest_row.y - y);
			if(reduction < best_reduction)
			{
				best_reduction = reduction;
				best_x = 0;
			}
		}
	}
	for(i = 0; i < dest_row.NodeID.size(); i++)
	{
		int current_x = ptrckt.nodes[dest_row.NodeID[i]].x_coord + ptrckt.nodes[dest_row.NodeID[i]].width - dest_row.lx;

		if(cell_displacement(dest_row.lx + current_x, dest_row.y, this_node) >= max_displacement * 0.9)
			continue;
		
		if(space_query(ptrckt, this_node, dest_row, current_x, answer))
		{	
			if(answer.space >= this_node.width) // Preferred way
			{
				int reduction = delta_HPWL(ptrckt, this_node.ID, current_x + dest_row.lx - x, dest_row.y - y);
				if(reduction < best_reduction)
				{
					best_reduction = reduction;
					best_x = current_x;
				}
			}
			else if(answer.available_space >= this_node.width) // Not preferred, because adjacent nodes would have been moved
			{
				int reduction = delta_HPWL(ptrckt, this_node.ID, current_x + dest_row.lx - x, dest_row.y - y) 
								+ 2 * (this_node.width - answer.available_space);
				if(reduction < best_reduction)
				{
					best_reduction = reduction;
					best_x = current_x;
				}
			}	
		}
	}
	return best_x;
}

void addBin2Queue(ckt & ptrckt, int curBinID, Candidate & temp, tinyRow & this_row)
{
	for(int row = 0; row < 9; row++)
	{
		tinyRow & dest_row = ptrckt.tinyRows[index_translate(curBinID, row)];
		if(!dest_row.isValid)
		{
			continue;
		}
		else
		{
			temp.dest_row.push(& dest_row);
		}
	}
}

bool insert2site_check(ckt & ptrckt, node & this_node, tinyRow & dest_row, int x)
{	
	assert(!this_node.isFixed);
	assert(dest_row.isValid);
	assert(x >= 0);
	assert(x <= dest_row.rx);
	int original_x;
	int original_y;

	query answer;
	if(space_query(ptrckt, this_node, dest_row, x, answer)) // Dummy Insert
	{
		if(answer.space >= this_node.width) // Can insert directly
		{
			if(answer.cellID_left == -1) // No cell on the left of x
			{
				original_x = this_node.x_coord;
				original_y = this_node.y_coord;

				this_node.x_coord = dest_row.lx;
				this_node.y_coord = dest_row.y;

				if(cell_displacement(this_node.x_coord, this_node.y_coord, this_node) > max_displacement)
				{
					this_node.x_coord = original_x;
					this_node.y_coord = original_y;
					return false;
				}	
			}
			else // At least one cell on the left of x
			{
				original_x = this_node.x_coord;
				original_y = this_node.y_coord;

				this_node.x_coord = ptrckt.nodes[answer.cellID_left].x_coord + ptrckt.nodes[answer.cellID_left].width;
				this_node.y_coord = dest_row.y;

				if(cell_displacement(this_node.x_coord, this_node.y_coord, this_node) > max_displacement)
				{
					this_node.x_coord = original_x;
					this_node.y_coord = original_y;
					return false;
				}

				assert(this_node.x_coord >= dest_row.lx);
			}

			// Can be more efficient
			dest_row.NodeID.push_back(this_node.ID);
			sort(dest_row.NodeID.begin(), dest_row.NodeID.end(), compareNodeID());
			fixNet(ptrckt, this_node);

			//move_node_in_row_check(ptrckt, this_node, this_node.x_coord, this_node.x_coord + answer.space - this_node.width, 1);
			return true;
		}
		else if(answer.available_space >= this_node.width) // Need to move adjacent cells
		{
			if(answer.space_left == -1) // right space must exist
			{
				assert(answer.space_right != -1);
				assert(answer.cellID_right != -1);
				node & right = ptrckt.nodes[answer.cellID_right];
				
				if(cell_displacement(right.x_coord + this_node.width - answer.space, right.y_coord, right) <= max_displacement)
				{
					right.x_coord += this_node.width - answer.space;
					fixNet(ptrckt, right);
				}
				else
				{
					return false;
				}


				if(answer.cellID_left == -1)
				{
					original_x = this_node.x_coord;
					original_y = this_node.y_coord;

					this_node.x_coord = dest_row.lx;
					this_node.y_coord = dest_row.y;

					if(cell_displacement(this_node.x_coord, this_node.y_coord, this_node) > max_displacement)
					{
						this_node.x_coord = original_x;
						this_node.y_coord = original_y;
						right.x_coord -= this_node.width - answer.space;
						return false;
					}

					assert(ptrckt.nodes[dest_row.NodeID[0]].x_coord >= dest_row.lx + this_node.width);
					assert(dest_row.lx >= dest_row.l_end);
				}
				else
				{
					assert(ptrckt.nodes[answer.cellID_left].isFixed);

					original_x = this_node.x_coord;
					original_y = this_node.y_coord;

					this_node.x_coord = ptrckt.nodes[answer.cellID_left].x_coord + ptrckt.nodes[answer.cellID_left].width;
					this_node.y_coord = dest_row.y;

					if(cell_displacement(this_node.x_coord, this_node.y_coord, this_node) > max_displacement)
					{
						this_node.x_coord = original_x;
						this_node.y_coord = original_y;
						right.x_coord -= this_node.width - answer.space;
						return false;
					}
				}

				fixNet(ptrckt, this_node);
				dest_row.NodeID.push_back(this_node.ID);
				sort(dest_row.NodeID.begin(), dest_row.NodeID.end(), compareNodeID());

				// move_node_in_row_check(ptrckt, this_node, this_node.x_coord, right.x_coord - this_node.width, 1);
				// move_node_in_row_check(ptrckt, right, this_node.x_coord + this_node.width, right.x_coord, 1);

				return true;
			}
			else if(answer.space_right == -1) // left space must exist
			{
				node & left = ptrckt.nodes[answer.cellID_left];
				assert(!left.isFixed);
				assert(answer.space + answer.space_left >= this_node.width);

				if(cell_displacement(left.x_coord - (this_node.width - answer.space), left.y_coord, left) <= max_displacement)
				{
					left.x_coord -= this_node.width - answer.space;
					fixNet(ptrckt, left);
				}
				else
				{
					return false;
				}

				original_x = this_node.x_coord;
				original_y = this_node.y_coord;

				this_node.x_coord = left.x_coord + left.width;
				this_node.y_coord = dest_row.y;

				if(cell_displacement(this_node.x_coord, this_node.y_coord, this_node) > max_displacement)
				{
					this_node.x_coord = original_x;
					this_node.y_coord = original_y;
					left.x_coord += this_node.width - answer.space;
					return false;
				}

				fixNet(ptrckt, this_node);
				dest_row.NodeID.push_back(this_node.ID);
				sort(dest_row.NodeID.begin(), dest_row.NodeID.end(), compareNodeID());

				return true;
			}
			else // both left and right space exist and movable
			{
				node & left = ptrckt.nodes[answer.cellID_left];
				node & right = ptrckt.nodes[answer.cellID_right];

				int original_left = left.x_coord;
				int original_right = right.x_coord;

				int left_move = answer.space_left;
				while(cell_displacement(left.x_coord - left_move, left.y_coord, left) >= max_displacement)
				{
					left_move--;
				}
				assert(left_move >= 0);

				left.x_coord -= left_move;

				assert(left.x_coord >= dest_row.lx);
				fixNet(ptrckt, left);

				int right_move = answer.space_right;
				while(cell_displacement(right.x_coord + right_move, right.y_coord, right) >= max_displacement)
				{
					right_move--;
				}

				assert(right_move >= 0);
				right.x_coord += right_move;
				assert(right.x_coord + right.width <= dest_row.rx);
				fixNet(ptrckt, right);

				if(answer.space + left_move + right_move < this_node.width)
				{
					left.x_coord = original_left;
					right.x_coord = original_right;
					return false;
				}

				original_x = this_node.x_coord;
				original_y = this_node.y_coord;

				this_node.y_coord = dest_row.y;

				for(int i = left.x_coord + left.width; i < right.x_coord - this_node.width; i++)
				{
					if(cell_displacement(i, this_node.y_coord, this_node) <= max_displacement)
					{
						this_node.x_coord = i;
						assert(this_node.x_coord + this_node.width <= right.x_coord);
						fixNet(ptrckt, this_node);
						dest_row.NodeID.push_back(this_node.ID);
						sort(dest_row.NodeID.begin(), dest_row.NodeID.end(), compareNodeID());
						return true;
					}
				}

				// Find no possible space...
				
				left.x_coord = original_left;
				right.x_coord = original_right;
				this_node.x_coord = original_x;
				this_node.y_coord = original_y;

				return false;
			}
		}	
	}
	return false;
}



